// https://leetcode.cn/problems/permutations-ii/

// 题干：给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

// 示例：输入：nums = [1,1,2]
//       输出：[[1,1,2],[1,2,1],[2,1,1]]

// 碎语：跟全排列1大框架相同，但是要考虑重复元素，因此要考虑剪枝
//       同一个节点的所有分支中，如果有相同元素，则只能选择一次
//       同个位置的元素只能出现一次
//  同个位置的好处理，设置一个数组check,check[i]==true,不合法，continue
//  可以只关心不合法的分支，也可以只关心合法的分支
//  判断是否处于同一层，数组给出的都是从小到大排序
//  因此可以判断nums[i]和nums[i-1]的关系，注意越界和同层
//  采用“判断什么时候不合法”来剪枝,记得sort一下

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    vector<vector<int>> ret;
    vector<int> path;
    bool check[9];
public:
    Solution()
    {
        memset(check, 0, sizeof(check));
    }

    vector<vector<int>> permuteUnique(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        dfs(nums);
        return ret;
    }

    void dfs(vector<int>& nums)
    {
        if (path.size() == nums.size()){
            ret.push_back(path);
            return ;
        }

        for (int i = 0 ; i < nums.size() ; i++){
            if (check[i] || (i != 0 && nums[i] == nums[i - 1] && !check[i - 1])){
                continue;
            }

            path.push_back(nums[i]);
            check[i] = true;
            dfs(nums);

            path.pop_back();
            check[i] = false; // 回溯
        }
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {1,1,2};

    vector<vector<int>> index = sol.permuteUnique(nums);
    for (auto arr : index){
        for (auto num : arr){
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}